#include "base_on_server.h"

using namespace BaseOnServer;
using namespace std::chrono;

u32 const K = 3;
u32 const LIMIT = 100;
u64 sol_cnt = 0;
std::time_t T = std::time(nullptr);
std::time_t max_T;
std::time_t sumTime = 0;
bool sat(Graph const &g, Set const &s)
{
    u32 n = s.data.size();
    auto f = [&s](u32 x)
    { return s.exist(x); };

    u32 edgeNum = 0;
    for (auto &v : s.data)
    {
        auto &es = g.edges[v];
        edgeNum += std::count_if(es.begin(), es.end(), f);
    }
    edgeNum /= 2;
    int limit = (n * (n - 1) / 2) - K;
    if (limit < 0 || edgeNum >= limit)
        return true;
    return false;
}

void cal(){
    auto avgTime = (float)sumTime/LIMIT;
    std::cout << "find " << LIMIT << " answer cost: " << sumTime << std::endl; 
    std::cout << "avg Time cost: " << avgTime <<std::endl;
    exit(0);
}
Set extend(Graph const &g, Set const &s)
{
    Set ret = s;
    u32 n = g.vrt_num;

    for (u32 i = 0; i < n; ++i) {
        if (!ret.exist(i)) {
            ret.add(i);
            if (sat(g, ret)) continue;
            ret.del(i);
        }
    }
    
    return ret;
}

struct EnumAlmostCoro
{
    enum State
    {
        Start,
        Resume,
        Finish
    };

    State cur; 
    Graph const &g; 
    Set const &s;   
    u32 v;          
    std::set<Set> save; 
    Set value;          
    Set pick, pos;      
    EnumAlmostCoro(Graph const &g_, Set const &s_, u32 v_) : cur(Start), g(g_), s(s_), v(v_)
    {
    }

   
    bool operator()()
    {
        u32 i = 1;
        if (cur == Finish)
            return false; 
        if (cur == Resume)
            goto CoroResume; 
        cur = Resume;

        while (i <= s.data.size())
        {
            while (s.next_pick(i, pos.data, pick.data))
            {
                value = pick + v;
                if (sat(g, value) && save.find(value) == save.end())
                {
                    save.insert(value);
                    return true;
                CoroResume:;
                }
            }
            i++;
        }
        cur = Finish;
        return false;
    }
};

void print(Set const &c)
{
    ++sol_cnt;
    auto T_now = std::time(nullptr) - T;
    sumTime +=T_now;
    if (T_now > max_T)
    {
        max_T = T_now;
    }
    std::cout << "[" << T_now << "s] No." << sol_cnt << " solution: " << c;
    std::cout << "max_duration: " << max_T <<std::endl;
    T = std::time(nullptr);
}

void enumAll(Graph &g, Set const &s, std::set<Set> &sol, bool output_flag = true)
{
    for (u32 i = 0; i < g.vrt_num; ++i)
    { 
        if (s.exist(i))
            continue; 

        auto enumAlmost = EnumAlmostCoro(g, s, i);
        Set &t = enumAlmost.value;                

        while (enumAlmost())
        {                         
            Set c = extend(g, t); 

            if (sol.find(c) == sol.end())
            {
                if (sol_cnt == LIMIT)
                {
                    cal();
                }
                sol.insert(c);
                if (output_flag)
                    print(c);
                enumAll(g, c, sol, !output_flag);
                if (!output_flag)
                    print(c);
            }
        }
    }
}

i32 main()
{
    Str input_path = "./data/high_graph.txt";
    std::ifstream input_stream(input_path);
    Graph g;
    std::set<Set> sol;

    input_stream >> g;
    input_stream.close();

    auto tik = system_clock::now();
    // Vec<u32> start_data{0};
    Set start_set;
    start_set = extend(g, start_set);
    sol.insert(start_set);
    print(start_set);

    enumAll(g, start_set, sol);
    auto tok = system_clock::now();

    auto duration = duration_cast<microseconds>(tok - tik);
	std::cout <<  "timeCost:" << double(duration.count()) * microseconds::period::num / microseconds::period::den 
     <<  std::endl;

    return 0;
}
